#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        unordered_map<string, int> mp;
        int n = s.size();
        int d = words[0].size();
        int len = d * words.size();
        for (auto& it : words) {
            mp[it]++;
        }

        vector<unordered_map<string, int>> res(d);

        for (int i = 0; i < d && i + len <= n; i++) {
            for (int j = i; j < i + len; j += d) {
                string str = s.substr(j, d);
                res[i][str]++;
            }
            if (res[i] == mp) {
                ans.emplace_back(i);
            }
        }

        for (int i = d; i + len <= n; i++) {
            int r = i % d;
            string pre = s.substr(i - d, d);
            string la = s.substr(i - d + len, d);
            res[r][pre]--;
            if (res[r][pre] == 0)res[r].erase(pre);
            res[r][la]++;
            if (res[r] == mp)ans.emplace_back(i);

        }

        return ans;
    }
};